//求根节点到叶子节点数字之和

class Solution {
    private:
    int sum;
public:
    void recursion(TreeNode* root,int& tmp)
    {
        if(root == nullptr)
        {
            return;
        }
        tmp = tmp*10 + root->val;
        if(root->left == nullptr && root->right == nullptr)
        {
            sum += tmp;
        }
        recursion(root->left,tmp);
        recursion(root->right,tmp);
        tmp /= 10;
    }
    int sumNumbers(TreeNode* root) {
        sum = 0;
        if(nullptr == root)
        {
            return sum;
        }
        int tmp = 0;
        recursion(root,tmp);
        return sum;
    }
};


//非递归实现二叉树的前序遍历、中序、后序
template <class T>
class TreeNode
{
public:
	TreeNode(const T& val = T())
		:_left(nullptr)
		,_right(nullptr)
		,_val(val)
	{
	}
	TreeNode<T>* _left;
	TreeNode<T>* _right;
	T _val;
};

vector<int> PrevOrder(TreeNode<int>* root)
{
	stack<TreeNode<int>*> s;
	vector<int> res;
	TreeNode<int>* cur = root;
	while (cur || !s.empty())
	{
		while (cur)
		{
			s.push(cur);
			res.push_back(cur->_val);
			cur = cur->_left;
		}
		//取出栈顶节点
		TreeNode<int>* top = s.top();
		s.pop();
		cur = top->_right;
	}
	return res;
}


vector<int> inOrder(TreeNode<int>* root)
{
	if (root == nullptr)
	{
		return vector<int>();
	}
	stack<TreeNode<int>*> st;
	vector<int> res;
	TreeNode<int>* cur = root;
	while (cur || !st.empty())
	{
		while (cur)
		{
			st.push(cur);
			cur = cur->_left;
		}
		TreeNode<int>* top = st.top();
		st.pop();
		res.push_back(top->_val);
		cur = top->_right;
	}
	return res;
}


void postOrder(TreeNode* root)
{
	stack<TreeNode*> st;
	vector<int> res;
	TreeNode* cur = root;
	TreeNode* prev = nullptr;
	while (cur || !st.empty())
	{
		while (cur)
		{
			st.push(cur);
			cur = cur->_left;
		}
		TreeNode* top = st.top();
		if (top->_right == nullptr || top->_right == prev)
		{
			res.push_back(top->_val);
			prev = top;
			st.pop();
		}
		else
		{
			cur = top->_right;
		}
	}
	return res;
}


//二叉搜索树与双向链表
//preOrder  前序遍历
//inOrder   中序遍历
//postOrder 后序遍历

class Solution {
public:
	void inOrder(TreeNode* root)
	{
		if(root == nullptr){
			return;
		}
		inOrder(root->left);
		if(head == nullptr)
		{
			head = root;
			cur = head;
		}
		else
		{
			cur->right = root;
			root->left = cur;
			cur = root;
		}
		inOrder(root->right);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) {
        inOrder(pRootOfTree);
		return head;
    }
private:
	TreeNode* head = nullptr; //记录双向链表的头节点
	TreeNode* cur = nullptr;  //

};
